#include <iostream>

using std::cout;

// 合并有序链表
struct ListNode
{
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

class Solution
{
public:
    ListNode *mergeTwoLists(ListNode *list1, ListNode *list2)

    {
        // 方法1：不递归
        if (list1 == nullptr || list2 == nullptr)
            return list1 == nullptr ? list2 : list1;
        ListNode *head = list1->val > list2->val ? list2 : list1;

        ListNode *cur1 = head->next;
        ListNode *cur2 = head == list1 ? list2 : list1;

        ListNode *cur = head;
        while (cur1 != nullptr && cur2 != nullptr)

        {
            if (cur1->val >= cur2->val)

            {
                cur->next = cur2;
                cur2 = cur2->next;
            }
            else
            {
                cur->next = cur1;
                cur1 = cur1->next;
            }
        }

        if (cur1 == nullptr)
            cur->next = cur2;

        if (cur2 == nullptr)
            cur->next = cur1;

        return head;
    }
};

int main(int argc, char const *argv[])
{
    ListNode *list1;
    ListNode *node11 = new ListNode(1, nullptr);
    ListNode *node12 = new ListNode(2, nullptr);
    ListNode *node13 = new ListNode(4, nullptr);
    list1 = node11;
    node11->next = node12;
    node12->next = node13;

    ListNode *list2;
    ListNode *node21 = new ListNode(1, nullptr);
    ListNode *node22 = new ListNode(3, nullptr);
    ListNode *node23 = new ListNode(4, nullptr);
    list2 = node21;
    node21->next = node22;
    node22->next = node23;

    Solution s;
    ListNode *list = s.mergeTwoLists(list1, list2);

    ListNode *cur = list;
    while (cur != nullptr)

    {
        cout << cur->val << " ";
    }
    cout << "-------\n";
    return 0;
}
